package datastructure.lineralist01;


import org.junit.jupiter.api.Test;

/**
 * @Filename: LinearListAlgorithmProblem
 * @Author: czh
 * @Data:2023/1/17 14:34
 * 线性表常见算法题
 */
public class LinearListAlgorithmProblem {
    public static void main(String[] args) {
        LinearListAlgorithmProblem linearListAlgorithmProblem = new LinearListAlgorithmProblem();
        // 1. 链表反转常规思路
//        linearListAlgorithmProblem.reverseList();
        // 1. 链表反转递归思路
        linearListAlgorithmProblem.display(linearListAlgorithmProblem.reverseByRecursion(linearListAlgorithmProblem.buildNode()));
    }

    /**
     * 题目：
     * 将两个递增的有序链表合并为一个递增的有序链表。
     * 要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
     * 分析:
     * 合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个节点，从第一个节点开始比较，
     * 当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后，如果两个表中的元素相等,只摘取La表中的
     * 元素，删除Lb表中的元素，这样确保合并后表中无重复的元素，当一个表达到表尾节点时，将非空表的剩余元素直接链接在Lc表
     * 的最后
     */
    @Test
    public void MergeList() {
    }

    /**
     * 链表反转测试类
     */
    @Test
    public void reverseList() {
        TestNode head = buildNode();
        TestNode reverse = reverse(head);
        display(reverse);
    }

    /**
     * 链表反转常规实现
     * 需求：
     * 原链表中数据为：1->2->3>4
     * 反转后链表中数据为：4->3->2->1
     * 实现思路：
     * 1. 判断链表的节点为null或者只有一个节点直接返回链表
     * 2. 初始化新空链表(ln)=null、被操作的链表(cur)等于头节点、被操作链表的下一个节点(next)，
     * (1) 先获取被操作链表的下一个节点(next=cur.next)
     * (2) 将结果链表的值赋值给被操作链表的next（cur.next=ln）
     * (3) 将被操作链表赋值给ln（ln=cur）
     * (4) 最后将被操作节点的下一个节点的值赋值给被操作节点(cur=next)
     */
    public TestNode reverse(TestNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        TestNode ln = null; // 新链表，结果链表
        TestNode cur = head; // 赋值给后面将要被操作的链表
        TestNode next; // 保存链表下一个的节点
        if (cur != null) {
            while (cur != null) {
                // 保存需要操作的链表的下一个节点
                next = cur.next;
                // 使用前插法添加到新链表的头部
                cur.next = ln;
                // 赋值结果链表
                ln = cur;
                // 将下一步要操作的节点链表重新赋值给cur
                cur = next;
            }
        }
        return ln;
    }

    /**
     * 链表反转递归实现
     * 需求：
     * 原链表中数据为：1->2->3>4
     * 反转后链表中数据为：4->3->2->1
     * 实现思路：
     */
    public TestNode reverseByRecursion(TestNode head) {
        // 1. 传入的参数的合法性 || 递归的终止条件
        if (head == null || head.next == null) {
            return head;
        }
        //2.递归
        TestNode newHead = reverseByRecursion(head.next);
        //3. 将后一个数组节点的指针指向前一个数据，并断开后一个节点指向后方的指针
        head.next.next = head;
        //4. 断开前一个数据指向后一个数据的指针，并指向null
        head.next = null;
        return newHead;
    }

    /**
     * 构建链表方法
     *
     * @return
     */
    public TestNode buildNode() {
        //构建结点
        TestNode first = new TestNode(1, null);
        TestNode second = new TestNode(2, null);
        TestNode third = new TestNode(3, null);
        TestNode fourth = new TestNode(4, null);

        //生成链表
        first.next = second;
        second.next = third;
        third.next = fourth;
        return first;
    }

    /**
     * 链表的显示方法
     *
     * @param node
     */
    public void display(TestNode node) {
        while (node != null) {
            // 最后一个
            if (node.next == null) {
                System.out.print(node.data);
            } else {
                System.out.print(node.data + "->");
            }
            node = node.next;
        }

        System.out.println();
    }
}

// 链表的节点类
class TestNode {
    public Integer data;
    public TestNode next;

    // 构造器
    public TestNode(Integer data, TestNode next) {
        this.data = data;
        this.next = next;
    }
}

